/**
 * @Question.Title: LFU 缓存
 * @Question.No: 460
 * @Author: DQ
 * @Date: 2021-04-22 20:56:42
 * @Description: 
 */
//请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。 
//
// 实现 LFUCache 类： 
//
// 
// LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 
// int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。 
// void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之
//前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。 
// 
//
// 注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。 
//
// 为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。 
//
// 当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。 
//
// 
//
// 示例： 
//
// 
//输入：
//["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "g
//et"]
//[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
//输出：
//[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
//
//解释：
//// cnt(x) = 键 x 的使用计数
//// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
//LFUCache lFUCache = new LFUCache(2);
//lFUCache.put(1, 1);   // cache=[1,_], cnt(1)=1
//lFUCache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
//lFUCache.get(1);      // 返回 1
//                      // cache=[1,2], cnt(2)=1, cnt(1)=2
//lFUCache.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
//                      // cache=[3,1], cnt(3)=1, cnt(1)=2
//lFUCache.get(2);      // 返回 -1（未找到）
//lFUCache.get(3);      // 返回 3
//                      // cache=[3,1], cnt(3)=2, cnt(1)=2
//lFUCache.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
//                      // cache=[4,3], cnt(4)=1, cnt(3)=2
//lFUCache.get(1);      // 返回 -1（未找到）
//lFUCache.get(3);      // 返回 3
//                      // cache=[3,4], cnt(4)=1, cnt(3)=3
//lFUCache.get(4);      // 返回 4
//                      // cache=[3,4], cnt(4)=2, cnt(3)=3 
//
// 
//
// 提示： 
//
// 
// 0 <= capacity, key, value <= 104 
// 最多调用 105 次 get 和 put 方法 
// 
//
// 
//
// 进阶：你可以为这两种操作设计时间复杂度为 O(1) 的实现吗？ 
// Related Topics 设计 
// 👍 379 👎 0

package dq.leetcode.editor.cn;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Objects;


public class LfuCache {
    public static void main(String[] args) {
        LFUCache lFUCache = new LfuCache().new LFUCache(2);
        lFUCache.put(1, 1);   // cache=[1,_], cnt(1)=1
        lFUCache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        System.out.println(lFUCache.get(1));// 返回 1
                              // cache=[1,2], cnt(2)=1, cnt(1)=2
        lFUCache.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                              // cache=[3,1], cnt(3)=1, cnt(1)=2
        System.out.println(lFUCache.get(2));// 返回 -1（未找到）
        System.out.println(lFUCache.get(3));// 返回 3
                              // cache=[3,1], cnt(3)=2, cnt(1)=2
        lFUCache.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                              // cache=[4,3], cnt(4)=1, cnt(3)=2
        System.out.println(lFUCache.get(1));
        System.out.println(lFUCache.get(3));// 返回 3
                              // cache=[3,4], cnt(4)=1, cnt(3)=3
        System.out.println(lFUCache.get(4));// 返回 4
                              // cache=[3,4], cnt(4)=2, cnt(3)=3
    }
        //leetcode submit region begin(Prohibit modification and deletion)
    class LFUCache {

        private int capacity;
        private int size;
        private int min;
        private Map<Integer, Node> map;
        private Map<Integer, LinkedHashSet<Node>> freqMap;
        public LFUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            this.min = 0;
            this.map = new HashMap<>();
            this.freqMap = new HashMap<>();
        }
        public int get(int key) {
            // 获取节点
            Node node = map.get(key);
            if(node == null) return  -1; // 获取失败
            int oldFreq = node.freq;

            //频率自增
            freqAdd(node);

            return node.val;
        }

        public void put(int key, int value) {
            if(capacity==0) return;
            Node node = map.get(key);
            //当前节点已经存在
            if(node != null){
                node.val = value;
                //频率自增
                freqAdd(node);
            }else{
                node = new Node(key, value);
                //缓存已满
                if(size == capacity){
                    removeLast();
                }
                //将节点放在不同频率的缓存中
                LinkedHashSet<Node> set = freqMap.get(node.freq);
                if(set == null){
                    set = new LinkedHashSet<>();
                    freqMap.put(1, set);
                }
                set.add(node);
                //初始化最小值
                min = 1;
                //加入集合
                map.put(key, node);
                size++;
            }
        }
        //节点频率自增，会在原来的集合中删除，并添加到新的集合中
        public void freqAdd(Node node){

            //将当前结点从原来的set中移除
            LinkedHashSet<Node> oldSet = this.freqMap.get(node.freq);
            oldSet.remove(node);
            //如果以前就是频率最小的话，并且移除之后，集合为空，将当前最小的频率加一
            if(node.freq == min && oldSet.isEmpty()){
                min++;
            }
            //频率自增
            node.freq++;
            //获取新集合，将当前结点加入到新的集合中
            LinkedHashSet<Node>set = freqMap.get(node.freq);
            if(set == null) {
                set = new LinkedHashSet<>();
            }
            set.add(node);
            freqMap.put(node.freq, set);
        }
        public void removeLast(){
            LinkedHashSet<Node> set = this.freqMap.get(min);
            //min会随着添加或访问来实时更新，因此set肯定不是空
            Node node = set.iterator().next();
            set.remove(node);
            map.remove(node.key);
            size--;
        }

        private class Node{
            int val;
            int freq = 1;
            int key;
            public Node(){};
            public Node(int key, int val){
                this.key = key;
                this.val = val;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                Node node = (Node) o;
                return key == node.key;
            }

            @Override
            public int hashCode() {
                return Objects.hash(key);
            }
        }
    }

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)

}